A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates generally to data processing environments and, more particularly, to system and methods for eager and opportunistic property enforcement in a database system.
2. Description of the Background Art
Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as xe2x80x9crecordsxe2x80x9d having xe2x80x9cfieldsxe2x80x9d of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information retrieved from or updated in such files, and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level.
DBMS systems have long since moved from a centralized mainframe environment to a de-centralized or distributed environment. Today, one generally finds database systems implemented as one or more PC xe2x80x9cclientxe2x80x9d systems, for instance, connected via a network to one or more server-based database systems (SQL database server). Commercial examples of these xe2x80x9cclient/serverxe2x80x9d systems include Powersoft(copyright) clients connected to one or more Sybase(copyright) Adaptive Server(copyright) Enterprise database servers. Both Powersoft(copyright) and Sybase(copyright) Adaptive Server(copyright) Enterprise (formerly Sybase(copyright) SQL Server(copyright)) are available from Sybase, Inc. of Dublin, Calif. The general construction and operation of database management systems, including xe2x80x9cclient/serverxe2x80x9d relational database systems, is well known in the art. See e.g., Date, C., xe2x80x9cAn Introduction to Database Systems, Volume I and II,xe2x80x9d Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.
One purpose of a database system is to answer decision support queries. A query may be defined as a logical expression over the data and the data relationships set forth in the database, and results in identification of a subset of the database. Consider, for instance, the execution of a request for information from a relational DBMS. In operation, this request is typically issued by a client system as one or more Structured Query Language or xe2x80x9cSQLxe2x80x9d queries for retrieving particular data (e.g., a list of all employees earning $10,000) from database tables on a server. In response to this request, the database system typically returns the names of those employees earning $10,000, where xe2x80x9cemployeesxe2x80x9d is a table defined to include information about employees of a particular organization. The syntax of SQL is well documented, see e.g., xe2x80x9cInformation Technologyxe2x80x94Database languagesxe2x80x94SQL,xe2x80x9d published by the American National Standards Institute as American National Standard ANSI/ISO/IEC 9075: 1992, the disclosure of which is hereby incorporated by reference.
SQL queries express what results are requested but do not state how the results should be obtained. In other words, the query itself does not tell how the query should be evaluated by the database management system. Rather, a component called the optimizer determines the xe2x80x9cplanxe2x80x9d or the best method of accessing the data to implement the SQL query. The query optimizer is responsible for transforming an SQL request into an access plan composed of specific implementations of the algebraic operator selection, projection, join, and so forth. Typically, this is done by generating many different access strategies, evaluating the cost of each, and selecting the access plan with the lowest overall cost, where xe2x80x9ccostxe2x80x9d is a metric that measures a combination of factors, including, but not limited to, the estimated amount of computational overhead, the number of physical Input/Output (xe2x80x9cI/Oxe2x80x9d) operations, and the response time. However, producing an optimal access plan for any given SQL query is a complex problem.
In a modern optimizer, efficient handling of orderings is of great importance to query optimization. Indeed, ordering-based techniques remain unavoidable in modern query processing, despite the effectiveness of hash-based techniques, see e.g., G. Graefe, xe2x80x9cThe Value of Merge-Join and Hash-Join in SQL Server,xe2x80x9d VLDB, 1999 and G. Graefe, R. Bunker, S. Cooper, xe2x80x9cHash Joins and Hash Teams in Microsoft SQL Server,xe2x80x9d VLDB, 1998. Ordering is intimately related to two fundamental components of relational database management systems: B-tree indices, at the implementation level, and the ORDER BY clause, at the language level. A B-tree index, besides providing direct access to database records or tuples, also provides an ordering. An ORDER BY clause explicitly requires an ordering. The naive solution, lazy sorting, is in many cases sub-optimal.
Given that ordering is important, there are many relational implementation techniques that rely on ordering and would benefit from its advanced handling. One example of a relational technique that would benefit from improved handling of orderings is merge join, the join algorithm that relies on its arguments being ordered on the equi-join clause columns. Several other relational database algorithms rely on ordered input including: merge union distinct, group sorted, distinct ordered and the min/max scalar aggregates.
An ordering is usually either provided by an index or enforced using a sorting operation or xe2x80x9csort node.xe2x80x9d An index being an alternative to the sort, the term xe2x80x9cordered inputxe2x80x9d is used instead of xe2x80x9csorted inputxe2x80x9d in this document. As the cost of a sorting operation is related to the amount of data to sort and as many relational algorithms preserve in their result some of the orderings provided by their arguments, sorting should be performed in the most efficient place that makes the ordering available up to the point where it is actually needed. In other words, a solution is required which provides for optimal placement of the sort node in an access plan. Because sorting is an expensive operation, optimizers typically preserve sub-plans that provide an xe2x80x9cinteresting orderingxe2x80x9d even if there are other cheaper (in terms of query execution cost) sub-plans that do not provide an interesting ordering. xe2x80x9cInteresting orderingxe2x80x9d involves consideration of the ordering of intermediate results from operator to operator. In particular, retaining a sub-plan that has an interesting ordering may enable a sort operation to be avoided, thereby reducing overall query execution cost compared to another sub-plan that does not have an interesting ordering. However, preserving these sub-plans reduces pruning and results in more sub-plans staying in the competition to create the best total plan. This results in an increase in the search space.
Among the ordering-based algorithms, distinct and group ordered are very inexpensive (in terms of query execution cost) implementations (non-blocking, on-the-fly, relying on their input having an ordering on the grouping columns) of an otherwise expensive operator. The distinct logical relational operator, also called delta-project, removes the duplicate tuples from its input; it groups on all of its columns. Its distinct ordered implementation relies on an ordered input to output a single tuple for each contiguous group of duplicates. The physical operator is xe2x80x9cnon-blockingxe2x80x9d or xe2x80x9con-the flyxe2x80x9d, as it does not need to read (and keep in some temporary storage) its whole input before output of its first tuple. This physical operator does not need to go back and visit an input tuple more than once. Instead, it keeps the current tuple and if the next tuple is equal (column wise), then it is discarded. All duplicates are contiguous in ordered input. Likewise, group ordered is a non-blocking vector aggregation physical operator that relies on its input to be ordered on the grouping columns. As all tuples in a group are thus guaranteed to be contiguous, the aggregate functions of each group can be computed on-the-fly, while traversing the input. Conversely sort is a xe2x80x9cblockingxe2x80x9d physical operator in that it may not produce its first result tuple before having seen the last tuple in its input, as the last tuple could be the first one in the requested sort order.
The sorting-based algorithms which are xe2x80x9cordering relatedxe2x80x9d (rather than xe2x80x9cordering-basedxe2x80x9d) are also relevant. As illustrated above, ordering-based algorithms take advantage of the ordering available in their inputs, but do not contain a sort. The sorting-based algorithms use in their implementation a sorting process. Within the sorting algorithm, it is inexpensive to eliminate duplicates, both while building the sorted runs and while merging them. Likewise, while sorting and eliminating duplicates on some columns, it is feasible and inexpensive (in terms of query execution cost) to incrementally compute aggregation functions on other columns (for a class of aggregation functions). This is the group sorting algorithm. These algorithms are less expensive than the sort, due to the beneficial outcome of the early reduction of the size of the sort runs, see e.g., D. Bitton, D. J. DeWitt, xe2x80x9cDuplicate Record Elimination in Large Data Files,xe2x80x9d TODS 8(2), 1983 and W. P. Yan, P. Larson, xe2x80x9cData reduction through early grouping,xe2x80x9d Proceedings of the 1994 IBM CAS Conference, Toronto, November, 1994. They provide an ordering on the grouping columns, in the same manner as a basic sort.
There are known eager/lazy grouping transformations, that allow the placement of one or several group nodes (i.e., grouping operations) in various legal places in the plan of a GROUP BY query. Likewise, when distinctness needs to be enforced (for instance for a SELECT DISTINCT) there are similar (and simpler) eager/lazy transformations. These are important optimizations, as grouping (and its simplified form, distinctiveness enforcement) both influences the plan and is influenced by the plan. It is influenced by the plan, as an ordered input allows use of a more efficient algorithm. It influences the plan by its execution cost (which can, for some of the grouping algorithms, be quite high) and also by the cardinality reduction in the grouped result (which decreases the cost of the parent nodes).
However, the tentative enforcement of grouping in all places where it is algebraically correct (see e.g., C. A. Galindo-Legaria, M. Joshi, xe2x80x9cOrthogonal Optimization of Subqueries and Aggregation,xe2x80x9d SIGMOD Conference, 2001) will increase the search space with various degrees of partially grouped sub-plans. In addition, as optimizers can be incorrect, one needs to constrain their choices with abstract plans (APs), see e.g., M. Andrei, P. Valduriez, xe2x80x9cUser-Optimizer Communication using Abstract Plans in Sybase ASE,xe2x80x9d VLDB, 2001. An abstract plan is a physical relational algebra expression that fully or partially describes the plan of a given query. The AP is given to the optimizer, which in turn generates a complying plan. Unfortunately, it is a known hard problem to build the validity proof of an abstract plan that is more complex than just giving the join order and the access methods such as an AP that implies order based algorithms and eager/lazy aggregation. However, building the validity proof of an abstract plan is not only useful but is also typically required in commercial implementations. It is useful as the sort, distinct, and group placement in a plan heavily affects performance. It may also be considered as mandatory as a commercial relational database management system (RDBMS) may not rely on the validity (with respect to the associated query) of an arbitrary abstract plan supplied by the user. Reliance on a given abstract plan supplied by the user can produce incorrect results, so the optimizer must be able to prove the correctness of an abstract plan in order to accept it.
What is required is a solution that will provide for improved handling of orderings enforcement by a query optimizer. The solution should provide for improved handling of orderings while avoiding an increase in the optimization search space or the execution cost of the query execution plan. Ideally, the solution should also implement the validity proofs needed for abstract plans that cover sorting, aggregation, and other more complex expressions. The present invention fulfills these and other needs.
The following definitions are offered for purposes of illustration, not limitation, in order to assist with understanding the discussion that follows.
Directed acyclic graph: A directed graph is a graph whose edges are ordered pairs of vertices (nodes). Each edge of a directed graph can be followed from one node (vertex) to the next. A directed acyclic graph is a directed graph where no path starts and ends at the same node.
Eager property enforcement: Eager property enforcement is a formalization and enhancement of the known xe2x80x9cinteresting propertiesxe2x80x9d enforcing technique which is applied in the system of the present invention to several physical properties, including ordering. More particularly, the eager property enforcement method of the present invention involves placing an enforcer in advance (a priori) when a new cheapest plan is added to an equivalence class. With this eager property enforcement approach, no enforcer needs to be added when a parent looks for a child node, as the enforcer is already present. Eager property enforcement relies upon knowing in advance the needs of all possible parents of any plans in an equivalence class. The method of the present invention for eager property enforcement is described in detail below in this document.
Enforceable properties: Enforceable properties are an extension of the enforcement of physical properties to also cover logical properties. Their application to ordering and aggregation is described below in this document.
Equivalence class or Eqc: An equivalence class or Eqc is a grouping of plans or sub-plans covering the same tables of a database. The characteristics of an equivalence class are that an equivalence class is identified by its set of underlying tables and that its candidate plans (or sub-plans) compete with each other to be part of the best total plan. For example, a sub-plan joining tables A and B is in a different equivalence class than a sub-plan joining tables B and C. The plan cache contains the set of created equivalence classes (Eqcs).
Logical property: A property that depends only on a logical expression is referred to as a logical property. A logical property can have the same value for a group of plans. For instance, the set of underlying tables is a logical property shared by all plans in an equivalence class. For queries that have no aggregation, the set of available attributes (columns) is an equivalence class level logical property and so is the set of projected columns (i.e., the ones needed by any parent equivalence class).
Maximal useful property: The eager property enforcement approach of the present invention is to model a set of corresponding interesting physical properties with a logical property which is referred to as the maximal useful property. The maximal useful property is used to represent the physical property of an enforcer and shares the same representation as the underlying physical property. The maximal useful property is used to represent an available property and can be compared, propagated, and so forth. The difference between the underlying (physical) property that is needed and its corresponding (logical) maximal useful property lies in their semantics. The maximal useful property is known in advance (a priori) for an equivalence class. The needed/useful property is known after the fact (a posteriori), for a given plan of that equivalence class.
Normalization: In the context of database design, normalization is the process of organizing data to minimize redundancy. In this document, normalization refers to the process of converting a database query into a simpler form that can be more efficiently analyzed by the query optimizer to deduce better data access strategies.
Opportunistic property enforcement: Opportunistic property enforcement is an aggregation optimization methodology of the present invention which takes advantage of both existing orderings and order enforcing within the eager ordering enforcement framework. The opportunistic property enforcement method of the present invention optimizes aggregation by taking advantage of the eager enforcement of ordering. This approach effectively applies the known aggregation transforms while avoiding an increase in the search space. Opportunistic property enforcement is described in detail below in this document.
Physical property: Properties that are known only for a given physical implementation of a logical relational expression are called physical properties. Not all properties of a plan depend only on the logical level relational expression describing it. The ordering of the data stream produced by the plan depends on the actual algorithms implementing the physical nodes. Some orderings are produced (e.g., by an index scan or a sort), some are preserved (e.g., the outer ordering of a join) and some are destroyed (e.g., the inner ordering of a join, with some exceptions). With respect to the optimization process, the physical properties are a posteriori in nature.
Plan cache: As an optimizer gradually builds alternative total plans (i.e., plans that have the same semantics as the original SQL query and that constitute candidates to become the final query execution plan); the optimizer keeps partial plans that are candidates to become part of the final query execution plan in a plan cache. In the currently preferred embodiment, the plan cache is implemented as a directed acyclic graph.
Predicate: In the context of relational databases a predicate is a truth-valued function, possibly negated, whose domain is a set of attributes and/or scalar values and whose range is {true, false, unknown}.
Property: The term property refers to a quantifiable characteristic or attribute of an object. In the context of relational databases, the term property refers to a quantifiable characteristic of a relational expression, sub-expression, or operator.
Query execution plan or QEP: A query execution plan or QEP is a demand-driven tuple stream xe2x80x9citeratorxe2x80x9d tree, which is a data structure that is interpreted by the relational database management system""s execution module or engine. This procedural construct is richer than a pure relational algebra expression. A QEP is a tree of relational algorithms applied to input tuple streams. A (logical level) relational expression is composed of (logical level) relational operators; it is a tree of logical nodes. A QEP or plan is composed of physical level relational operators (or algorithms); it is a tree of physical nodes. These physical operators are nodes in a tree that have children. A tree of physical operators is a sub-plan or the full (final) plan. A plan is the full plan if it covers the total semantics of the query (i.e., if the result set of the root node of the plan tree delivers the result set of the query). In this document, references to a QEP or plan refer to a query execution plan (or a portion thereof) unless otherwise indicated by the context.
Sub-plan or plan fragment: A sub-plan or plan fragment is a tree of physical operators that is a portion of a (full) query execution plan (as defined above) or a candidate to become a portion of a (full) query execution plan.
SQL: SQL stands for Structured Query Language, which has become the standard for relational database access, see e.g., xe2x80x9cInformation Technologyxe2x80x94Database languagesxe2x80x94SQL,xe2x80x9d published by the American National Standards Institute as American National Standard ANSI/ISO/IEC 9075: 1992, the disclosure of which is hereby incorporated by reference. For additional information regarding SQL in database systems, see e.g., Date, C., xe2x80x9cAn Introduction to Database Systems, Volume I and II,xe2x80x9d Addison Wesley, 1990, the disclosure of which is hereby incorporated by reference.
A database system providing methods for eager and opportunistic property enforcement is described. A method for eager ordering enforcement enabling improved query optimization commences with receipt of a query that requests data from a database and requests the data to be ordered. Plan fragments are generated for obtaining the data requested by the query. Plan fragments covering the same tables of the database are grouped together in classes. For each class, the particular plan fragment having the lowest execution costs for obtaining the requested data is determined. Any required ordering enforcement operator is added to this particular plan fragment to provide the needed ordering of data.
A method for eager and opportunistic enforcement enabling improved query optimization, commences with the receipt of a query for data from a database which requests ordering and grouping of the data. Sub-plans are generated for obtaining data requested by the query. Each of these sub-plans comprises a portion of an overall query execution plan. The sub-plans that are generated are organized into classes based upon tables covered by each sub-plan. For each class, a particular sub-plan having the lowest execution costs is determined. If grouping is not required at a given class, an operator enforcing ordering is added to this particular sub-plan. However, if grouping is required at the given class, an operator enforcing both grouping and ordering is added to this sub-plan.